Round Overview
Discuss this match
In Division 1, the match got off to a brisk start with fast solutions pouring in for both the easy and the medium and the scores being tightly packed. ACRush submitted a much faster hard solution than the others, and opened up a comfortable lead. However, he re-submitted his medium with about half an hour to go to level the playing field once again. At the end of the coding phase, barring the surprise leader yifenfei, the rest of the top 10 comprised the usual suspects separated by less than a hundred points or just 2 successful challenges - setting the stage for an exciting challenge phase where many people were in with a shot for the top place. However, yifenfei was taken down almost immediately and Petr racked up 175 challenge points in quick time to put things beyond doubt. The system tests saw many of the solutions go down, but after the dust settled it was Petr and ACRush on top (yet again) and gawry in third place. With this win, Petr edged out ACRush for the top rank by a single rating point! As this was the last SRM before the TopCoder Open, the rivalry is now set to continue at the TCO.
DifferentStrings
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 870 / 1100 (79.09%) |
Success Rate | 714 / 870 (82.07%) |
High Score | pratyush19 for 249.95 points (0 mins 25 secs) |
Average Score | 185.55 (for 714 correct submissions) |
We add new characters at the start or end to have strings of same length.So,newly added character will be of respective B String’s character to keep the difference to minimum. Adding a new character to A-String can cause someother characters to mismatch( Logically, calculating the difference for each character added to start of string would suffice).
1
2
3
4
5
6
7
8
9
10
11
12
public int minimize(String A, String B) {
int result = 999999999;
for (int shift = 0; shift <= (B.length() - A.length()); shift++) {
int difference = 0;
for (int i = 0; i < A.length(); i++) {
if (A.charAt(i) != B.charAt(i + shift))
difference++;
}
result = Math.min(result, difference);
}
return result;
}
PaperAndPaintEasy
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 471 / 1100 (42.82%) |
Success Rate | 74 / 471 (15.71%) |
High Score | stFlint for 418.80 points (13 mins 2 secs) |
Average Score | 285.36 (for 74 correct submissions) |
The problem involved very little implementation issues, once the math behind the problem was figured out. To summarize the problem statement, a rectangular sheet of paper is subjected to a series of folds; we are given some coordinates in the final sheet of paper. We need to find the number of uncolored squares. To rephrase the problem, we need to find the number of colored squares and subtract them from the total area.
Now, let us analyze step 1. We fold the paper at x=xfold. If we visualize, after the fold, the paper can be divided into two sections, along the x-axis. In the range of coordinates from 0 to xfold-1 (both inclusive), there is one cell beneath each cell visible on the surface. In other words, any cell colored on top from [0,xfold-1], will actually color 2 cells. The range of cells in [xfold,width-1], do not overlap any other cell. So, any colored cell in [xfold,width-1] will color only a single cell.
There is one pitfall, however that must be watched out for. The above analysis is valid only when xfold<=(width/2). When xfold>(width/2), a part of the folded paper will stick out of the boundary. But however, if we flip the paper, folded in such a manner,upside-down, it will be equivalent to the fold obtained when x=width-xfold. Hence the begining of the algorithm should check for xfold, and update the intervals accordingly.
Now we come to the analysis of the second step. The yfold. The paper is folded along y-axis (cnt+1) times.This fold will affect all cells in the paper.For ease of understanding, assume that no xfold was done before. If only the yfold is performed (cnt+1) times, then each cell in the folded paper will have cnt cells beneath it. Or each colored cell on top, will actually result in (cnt+1) colored cells.
Now since both the x-fold and y-fold have been performed one after the other, the entire folded paper will be divided into 2 regions - each cell in [xfold,width-1] will color (cnt+1) cells. Each cell in [0,xfold-1] will color 2*(cnt+1) cells, (because of earlier extra xfold). We need not bother with the height of the resulting rectangle as the given (y1, y2) will always be within the limits.
Now, to solve the actual problem. The entire folded paper has 2 regions. Let us denote, as SCL (number of cells, colored by coloring a single on the left [region 1]) and SCR (number of cells, colored by coloring a single cell on the right [region 2]);
We have
SCR=(cnt+1);
SCL=2*SCR;
Now, the given range (x1,x2) can -
Case 1: Lie entirely within [0,xfold-1].[region 1]
Case 2: Lie entirely within [xfold, width-1].[region 2]
Case 3: Overlap with region 1 and region 2
Case 1 is easy, as the answer is (x2-x1)*(y2-y1)*SCL;
Case 3 is also easy as the answer is (x2-x1)*(y2-y1)*SCR;
For case 2, we need to define two variables, t1,t2 -
t1 = (y2-y1)*(xf-x1)*SCL;
t2 = (y2-y1)*(x2-xf)*SCR;
ans=t1+t2;
The return value will be (width*height)-ans;
In all these multiplications and additions, make sure that all variables are of datatype long (64 bits). As there is a possibility of overflow. Almost all passed solutions, used a variant of the above approach.
PerfectPermutationHard
Problem Details
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 22 / 1100 (2.00%) |
Success Rate | 3 / 22 (13.64%) |
High Score | lcjh for 643.74 points (24 mins 9 secs) |
Average Score | 496.93 (for 3 correct submissions) |
PerfectPermutation
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 447 / 560 (79.82%) |
Success Rate | 413 / 447 (92.39%) |
High Score | murphydog for 249.41 points (1 mins 23 secs) |
Average Score | 189.22 (for 413 correct submissions) |
A “perfect” permutation is a permutation that consists of one cycle. Two cycles in a permutation can be “glued” by changing two elements. For example (123)(45) can be transformed into (12345) by saying that 3->4 (instead of 3->1) and 5->1 (instead of 5->4). In general, k cycles can be glued by changing k elements. So the problem asks for the number of cycles in the given permutation (unless that number is one, in which case 0 should be returned).
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 384 / 560 (68.57%) |
Success Rate | 192 / 384 (50.00%) |
High Score | Petr for 477.13 points (6 mins 16 secs) |
Average Score | 315.07 (for 192 correct submissions) |
Let’s define the country as a graph, the cities become vertexes and the roads between each pair of cities would become undirected edges. Some analysis is required before solving the problem, first, let’s divide the graph in different groups of connected vertexes, what in graph theory is called a connected component, it would be clear that the objective of the problem becomes to connect these connected components with each other until there is only one connected component.
These connected components might or might not have redundant edges. A redundant edge would be defined as an edge that you could remove from the component in a way that the vertexes in the component remain connected. Imagine that there were two connected components with at least one redundant edge, it is possible to apply the operation defined by the problem statement on two redundant edges (one for each component), show that this procedure will result in a bigger connected group of cities, and that after this operation, the new component will contain at least one redundant edge. Generalizing this method allows us to have an algorithm that solves the special case in which all of the connected components contain at least one redundant edge, just repeat this operation until there is only one component remaining.
We still need to deal with the cases involving connected components with no redundant edges, if we took two of these components, there would be no way to join them into a single component - any pair of edges you choose would result in two different connected components. However, it is still possible to join a component with no redundant edges with a component that contains redundant edges, doing this operation will consume one of the redundant edges. If there is only one redundant edge in the second component, the new component will be one with no redundant edges.
We can now draw conclusions:
- 2 Components with redundant edges can become one by performing one operation.
- 2 components with no redundant edges cannot become one.
- 1 component with no redundant edges can be added to another with K redundant edges, the result is a connected component with K-1 redundant edges.
These conclusions are enough to build an algorithm, first calculate the connected components and count the number of redundant edges in each one, then try to join non-redundant connected components with redundant ones, until it is not possible to remove any more of the components that contain no redundant edges. After this step:
- If there is only one single component remaining, return the number of operations performed so far.
- If there are only N components remaining and each of them contains redundant edges, return ((operations performed so far) + N).
- Else return -1 as there are components that cannot be joined together.
There is a special case, if there are any isolated vertexes, it is not possible to join them with other vertexes, so the return value is -1. A part of the implementation, to count the number of redundant edges in a component could cause incorrect solutions. There are many methods to do this, for example, calculate a minimum spanning tree for the component and count the number of edges not in the tree. Another method is to simply mark all the edges used when performing a dfs, and then count the edges that were not necessary.
C++ code follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
#include <string>
#include <memory>
using namespace std;
struct StrangeCountry {
int n;
vector < string > g;
int comps; //number of components with redundant edges
int cextra[50]; //number of redundant edges per component
int ccount[50]; //number of vertexes in a component
int noextra; //number of components with no redundant edges
bool visited[50];
bool useful[50][50]; //is the edge useful?
void dfs(int comp, int parent, int x, int ind = 0) {
if (visited[x]) return;
visited[x] = true;
ccount[comp]++;
for (int i = n; i--;)
if ((i != parent) && (g[x][i] == 'Y') && !visited[i]) {
useful[x][i] = useful[i][x] = true;
dfs(comp, x, i, ind + 1);
}
// count non-useful (redundant) edges:
for (int i = x + 1; i < n; i++)
if ((g[x][i] == 'Y') && !useful[x][i])
cextra[comp]++;
}
int transform(vector < string > g) {
memset(useful, 0, sizeof(useful));
comps = 0;
n = g.size();
this - > g = g;
noextra = 0;
fill(visited, visited + n, false);
for (int i = n; i--;)
if (!visited[i]) {
cextra[comps] = 0;
ccount[comps] = 0;
dfs(comps, -1, i);
if (ccount[comps] == 1) //isolated vertex
return -1; // impossible
if (cextra[comps] == 0) //the component got
noextra++; //no redundant edges
else
comps++;
}
int total = 0; //total operations performed
//join the components with no redundant edges
// with the last of the components with redundant edges
// until it is not possible anymore:
while (noextra && comps) {
total++;
if (cextra[comps - 1] == 1)
comps--;
else
noextra--,
cextra[comps - 1]--;
}
if ((noextra == 1) && (comps == 0))
return total;
if (noextra > 0)
return -1;
return total + comps - 1;
}
};
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 51 / 560 (9.11%) |
Success Rate | 28 / 51 (54.90%) |
High Score | ACRush for 786.37 points (15 mins 43 secs) |
Average Score | 482.38 (for 28 correct submissions) |